package dfs;


public class AdditiveNumber306 {
    public boolean isAdditiveNumber(String num) {
        for (int i = 1; i < num.length(); i++) {
            for (int j = i + 1; j < num.length(); j++) {
                String first = num.substring(0, i);
                if (first.length() > 1 && first.charAt(0) == '0') {
                    return false;
                }
                String second = num.substring(i, j);
                if (second.length() > 1 && second.charAt(0) == '0') {
                    continue;
                }
                if (check(first, second, j, num)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean check(String first, String second, int index, String num) {
        String target = add(first, second);
        for (int i = index + 1; i <= num.length(); i++) {
            String a = num.substring(index, i);
            if (a.length() > 1 && a.charAt(0) == '0') {
                continue;
            }
            if (target.equals(a)) {
                if (i == num.length()) {
                    return true;
                }
                return check(second, a, i, num);
            }
        }
        return false;
    }


    private String add(String a, String b) {
        StringBuilder aa = new StringBuilder(a);
        a = aa.reverse().toString();
        StringBuilder bb = new StringBuilder(b);
        b = bb.reverse().toString();
        if (a.length() < b.length()) {
            String tmp = a;
            a = b;
            b = tmp;
        }
        StringBuilder sb = new StringBuilder();
        int add = 0;

        for (int i = 0; i < a.length(); i++) {
            int r = 0;
            if (i < b.length() ) {
                r = a.charAt(i) + b.charAt(i) + add - '0' - '0';
            } else{
                r = a.charAt(i)+add -'0';
            }
            add = r/10;
            sb.append(r%10);
        }
        if(add!=0){
            sb.append(add);
        }
        return sb.reverse().toString();
    }
}
